The present invention relates in general to digital logic devices and in particular to an asychronous state machine permitting multiple input change and sequenced outputs.
The next state of a state machine is a function of the current state of the machine together with current states of any externally generated inputs. Digital logic state machines are typically characterized by a state register, for storing data representing the current state of the machine, and a block of combinational logic for generating the data representing the next state of the machine based on the combination of applied inputs and the current state data stored in the state register. The next state data is applied to the input of the state register and the machine "changes state" when a clock pulse applied to the gate control of the state register causes it to replace the stored current state data with the output data from the combinational logic block. Digital state machines are often used as programmable control devices with the current state data being used to control external events and with the input data being generated by sensing devices.
In a "synchronous" state machine, the clock pulse applied to the gate control of the state register is generated independently of the input changes (usually periodically) and input changes are permitted only during certain intervals between the clock pulses. In an "asychronous, single input change" state machine, the clock pulses are generated following detection of an input change, rather than independent of input changes. Only one input signal may change at a time and consecutive input changes must be separated by the minimum time required for the machine to change state in response to the changed input. In an "asychronous, multiple input change" state machine, the clock pulse is also generated following detection of an input change but a group of several input signals may change within an interval of duration D.sub.1 and be treated as "simultaneous" input events for purposes of effecting a state change, provided that such groups are separated by the minimum time (D.sub.2) required for the machine to change state in response to the changed inputs.
It follows that the theoretical minimum possible time between changes in a multiple input asynchronous state machines is D.sub.1 +D.sub.2. However, in the prior art, due to the nature of the mechanisms for generating the clocking pulses, a cycle must be at least as long as 1.5D.sub.1 (or more in some designs) when the last input change occurs as long as D.sub.1 after the first. Since in many applications 0.5D.sub.1 is much greater than D.sub.2, the latter practical constraint often degrades system performance.
In multiple change input asychronous state machines of the prior art, the inputs are applied to a change detector which produces a signal on detection of a state change in any of the inputs. This signal is then delayed by a delaying circuit and then applied to the state register as the clocking signal. The clocking signal is also fed back to the change detector to turn off the state change signal. The clocking pulse is delayed after detection of the first input change by a fixed delay time, proportional to D.sub.1, which must be sufficient to allow for the worst case multiple input situation wherein the the last input change is expected to occur the longest time after the first. However, the fixed delay time may be longer than necessary to allow for multiple input changes as may occur when the machine is in other states. Since the state machine cycle time is related to the fixed delay time, the state change cycle time of the prior art state machines is dependent only on the worst case state change situation. Therefore if any one state change requires a very long cycle time, all other state changes require a similar long cycle time and the system speed is further degraded.
Sometimes it is desirable that an input change initiate a sequence of output state changes, rather than to simultaneously initiate a set of events. However, since the clocking of the state changes occurs only on a change in input states, only the first machine state of the sequence could be reached. In the prior art this problem was solved by feeding back the current state of the state machine to the input change detector such that changes in output state would result in subsequent state changes even in the absence of any change in input states. However this approach further degrades system speed by requiring the system to cycle one extra time for each sequence or isolated state change such that the machine state stabilizes.